package Tree;

import java.util.Scanner;
import java.util.Stack;
import java.util.Random;

public class Main {
	char numberch;
	static int i = 0;
	static int height = 0;

	public static BTree InfixToBinaryTree(String infix, int infixL)
	{
		Stack stack = new Stack ();
		Stack treeStack = new Stack ();

		for (int i = 0; i <= infixL; i++)
		{
			if (((infix.charAt(i) >= 'a') && (infix.charAt(i) <= 'z')) || ((infix.charAt(i) >= 'A') && (infix.charAt(i) <= 'Z'))||((infix.charAt(i) >= '0') && (infix.charAt(i) <= '9'))) 
			{
				treeStack.push(BTree.ConsBT(infix.charAt(i), null, null));
				System.out.println("push -> " + infix.charAt(i));
				continue;
			}

			if ((infix.charAt(i) == '*')||(infix.charAt(i) == '/')||(infix.charAt(i) == '+')||(infix.charAt(i) == '-'))
			{
				int priority  = getPriority(infix.charAt(i));
				System.out.println("push -> " + infix.charAt(i));
				char a = (char) stack.firstElement();
				while ((!stack.empty()) && ( getPriority(a) >= priority)) 
				{
					a = (char) stack.pop();
					BTree test = (BTree) treeStack.pop();
					BTree test2 = (BTree) treeStack.pop();
					
					treeStack.push(BTree.ConsBT(a, test, test2));
				}

				stack.push(infix.charAt(i));
			}

			if (infix.charAt(i) == '(') 
			{
				stack.push(infix.charAt(i));
				System.out.println("push -> " + infix.charAt(i));
				continue;
			}

			if (infix.charAt(i) == ')')
			{
				char b = (char) stack.lastElement();
				
				while (b != '(') 
				{
					b = (char) stack.pop();
					BTree test = (BTree) treeStack.pop();
					BTree test2 = (BTree) treeStack.pop();
					treeStack.push(BTree.ConsBT(b, test2, test));
					b = (char) stack.lastElement();
				}
				stack.pop();
				continue;
			}
		}
		BTree c = (BTree) treeStack.firstElement();
		return c;
	}
	
	public static void printResult (BTree result)
	{
		System.out.println("");
		System.out.println("Tree prefix :: ");
		LKPprintBT(result, height);
		System.out.println("");
	}

	public static void LKPprintBT (BTree b, int height)
	{	
		if (!BTree.isNull(b)) 
		{
			if (!BTree.isNull(BTree.Right(b)))
			{
				LKPprintBT(BTree.Right(b),height+1);
			}

			for (int i = 0; i < height; System.out.print("  "), i++);
			System.out.println(BTree.RootBT(b));
			
			if (!BTree.isNull(BTree.Left(b)))
			{
				LKPprintBT(BTree.Left(b),height+1);
			}
		}
	}

	public static void PrintFormula (BTree b)
	{
		if (!BTree.isNull(b)) 
		{
			if (!BTree.isNull(BTree.Left(b)))
			{
				System.out.print("(");
				PrintFormula(BTree.Left(b));	
			}
			System.out.print(BTree.RootBT(b));

			if (!BTree.isNull(BTree.Right(b)))
			{
				PrintFormula(BTree.Right(b));
				System.out.print(")");
			}
		}
	}

	public void TreeCheckKLP (BTree b)
	{	
		if (!BTree.isNull(b)) 
		{
			if ( ('a' <= b.info) && (b.info <= 'z'))
			{
				numberch = b.info;
			}
			TreeCheckKLP (BTree.Left(b));
			TreeCheckKLP (BTree.Right(b));
		}
	}
	
	public static void WprintLPK (BTree b)
	{	
		if (!BTree.isNull(b)) 
		{
			WprintLPK (BTree.Left(b));
			WprintLPK (BTree.Right(b));
			System.out.print(BTree.RootBT(b));
		}
	}
	
	public static int getPriority(char s)
	{
		if ((s == '(')||(s == ')'))
		{
			return 0;
		}
		if ((s == '*')||(s == '/'))
		{
			return 2;
		}
		if ((s == '+')||(s == '-'))
		{
			return 1;
		}
		return 3;
	}

	public static BTree Peredelka(BTree result)
	{
		char chit;
		int k;
		if (!BTree.isNull(result))
		{
			chit = BTree.RootBT(result);
			switch (chit)
			{
			case '+':
						for (k = 0; i != k; k++)
						{
							System.out.print(" ");
						}
						System.out.println("Go to the left subtree: " + BTree.RootBT(BTree.Left(result)));
						i++;
						result.lt = Peredelka(BTree.Left(result));
						i++;
						if (BTree.RootBT(BTree.Left(result)) == '0')
						{
							i--;
							System.out.println("In the left node was found item '0' and node was replaced on the subtree " + BTree.RootBT(BTree.Right(result)));
							return BTree.Right(result);
						}
						if (BTree.RootBT(BTree.Right(result)) == '0')
						{
							i--;
							System.out.println("In the right node was found item '0' and node was replaced on the subtree " + BTree.RootBT(BTree.Left(result)));
							return BTree.Left(result);
						}
						i--;
						for (k = 0; i != k; k++)
						{
							System.out.print(" ");
						}
						System.out.println("Go to the right subtree: " + BTree.RootBT(BTree.Right(result)));
						i--;
						result.rt = Peredelka(BTree.Right(result));
				break;
			case '-':
						for (k = 0; i != k; k++)
						{
							System.out.print(" ");
						}
						
						System.out.println("Go to the left subtree:" + BTree.RootBT(BTree.Left(result)));
						i++;
						result.lt = Peredelka(BTree.Left(result));
						i++;
						if (BTree.RootBT(BTree.Right(result)) == '0')
						{
							i--;
							System.out.println("In the left node was found item '0' and node was replaced on the subtree " + BTree.RootBT(BTree.Right(result)));
							return BTree.Left(result);
						}
						i--;
						for (k = 0; i != k; k++)
						{
							System.out.print(" ");
						}
						System.out.println("Go to the right subtree:" + BTree.RootBT(BTree.Right(result)));
						i--;
						result.rt = Peredelka(BTree.Right(result));
				break;
			case '*':
						for (k = 0; i != k; k++)
						{
							System.out.print(" ");
						}
						i++;
						System.out.println("Go to the left subtree:" + BTree.RootBT(BTree.Left(result)));
						i++;
						result.lt = Peredelka(BTree.Left(result));
						if (BTree.RootBT(BTree.Left(result)) == '0')
						{
							i--;
							System.out.println("In the left node was found item '0' and node was replaced on the subtree 0");
							result.rt.info = '0';
							result.rt.lt = null;
							result.rt.rt = null;
							return BTree.Right(result);
						}
						if (BTree.RootBT(BTree.Right(result)) == '0')
						{
							i--;
							System.out.println("In the right node was found item '0' and node was replaced on the subtree 0");
							result.lt.info = '0';
							result.lt.lt = null;
							result.lt.rt = null;
							return BTree.Left(result);
						}
						if (BTree.RootBT(BTree.Left(result)) == '1')
						{
							i--;
							System.out.println("In the left node was found item '1' and node was replaced on the subtree " + BTree.RootBT(BTree.Right(result)));
							return BTree.Right(result);
						}
						if (BTree.RootBT(BTree.Right(result)) == '1')
						{
							i--;
							System.out.println("In the right node was found item '1' and node was replaced on the subtree " + BTree.RootBT(BTree.Left(result)));
							return BTree.Left(result);
						}
						i--;
						for (k = 0; i != k; k++)
						{
							System.out.print(" ");
						}
						System.out.println("Go to the left subtree:" + BTree.RootBT(BTree.Right(result)));
						i--;
						result.rt = Peredelka(BTree.Right(result));
				break;
			}
		}	
		return result;
	}
	
	public static void main(String[] args) {
		 char pressedKey = 0, Key = 0; 
		 char[] a = new char[100];

		 String ch, prm;

		 BTree result = null, result2 = null;

		 int prefixL = 0, n1 = 100, n = 0;

		 System.out.println("Enter the formula with infix account");
		 Scanner sc = new Scanner(System.in);
		 String s = sc.nextLine();
		 for (n = 0; n < s.length(); n++)
		 {
			 a[n] = s.charAt(n);
		 }
		 System.out.println("The length of the entered formula = " + n);
		 System.out.println("Entered formula :: ");

		 for (int i = 0; i < n; i++) 
			System.out.print(a[i]);
		 System.out.println("");
						
		 result = InfixToBinaryTree(s, n-1);
			
		 printResult (result);
		 System.out.println("The fofmula for this tree:");
		 PrintFormula(result);
		 System.out.println("");
		 System.out.println("");
		 System.out.println("Enumeration of the tree nodes in order LPK:");
		 WprintLPK(result);
		 System.out.println("");
		 System.out.println("");
		 System.out.println("Received after processing of tree :");
		 result2 = Peredelka(result);
		 printResult (result2);
	}
}